package exercises.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/">
 * 剑指 Offer 30. 包含min函数的栈</a>
 *
 * @author or2
 * @Description 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * @create 2021年09月19日 时间: 20:52
 */
public class Offer30 {

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.min();
     */
    private static class MinStack {

        private Deque<Integer> stack;
        private Deque<Integer> stackMin;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            stack = new LinkedList<>();
            stackMin = new LinkedList<>();
        }

        public void push(int x) {
            stack.push(x);
            if (stackMin.isEmpty()) {
                stackMin.push(x);
            } else {
                if (stackMin.peek() >= x) {
                    stackMin.push(x);
                }
            }
        }

        public void pop() {
            if (stack.isEmpty()) {
                return;
            }
            if (stack.pop().equals(stackMin.peek())) {
                stackMin.pop();
            }
        }

        public int top() {
            if (stack.isEmpty()) {
                return -1;
            }
            return stack.peek();
        }

        public int min() {
            if (stack.isEmpty()) {
                return -1;
            }

            return stackMin.peek();
        }
    }

}
